package org.example.datastruct;

import com.alibaba.fastjson.JSON;
import com.google.common.collect.Lists;

import java.io.Serializable;
import java.util.List;

/**
 * 二叉树
 */
public class BinaryTreeTest {


    public static void main(String[] args) {

        List<Integer> dataList = Lists.newArrayList(7, 8, 4, 3, 5, 10, 9, 6);
        TreeNode<Integer> tree = createBinTree(dataList);

        System.out.print("原始树：\n" + JSON.toJSONString(tree, true));

        System.out.print("\n先序：");
        pre(tree);

        System.out.print("\n中序：");
        mid(tree);

        System.out.print("\n后序：");
        after(tree);

        System.out.println("\n查找:\n" + JSON.toJSONString(getNode(tree, 8), true));

        System.out.println("\n删除:\n" + JSON.toJSONString(remove(tree, 8), true));
    }


    /**
     * 构建一颗二叉树
     *
     * @param dataList 数据列表
     * @return 二叉树
     */
    private static TreeNode<Integer> createBinTree(List<Integer> dataList) {

        TreeNode<Integer> tree = null;
        for (int data : dataList) {
            if (tree == null) { // 头结点
                tree = new TreeNode<>(data, null, null, null);
                continue;
            }
            insertNode(tree, data);
        }
        return tree;
    }

    /**
     * 结点插入数据，递归方式
     *
     * @param node 当前结点
     * @param data 数据
     */
    private static void insertNode(TreeNode<Integer> node, Integer data) {

        TreeNode<Integer> next;
        if (node.data < data) { // 右树
            if (node.right == null) {
                node.right = new TreeNode<>(data, null, null, node);
                return;
            }
            next = node.right;
        } else { // 左树
            if (node.left == null) {
                node.left = new TreeNode<>(data, null, null, node);
                return;
            }
            next = node.left;
        }

        insertNode(next, data); // 递归
    }

    /**
     * 先序遍历
     *
     * @param tree 二叉树
     */
    private static void pre(TreeNode<Integer> tree) {

        if (null != tree) {
            System.out.print(tree.data + " ");
            pre(tree.left);
            pre(tree.right);
        }
    }

    /**
     * 中序遍历
     *
     * @param tree 二叉树
     */
    private static void mid(TreeNode<Integer> tree) {

        if (null != tree) {
            pre(tree.left);
            System.out.print(tree.data + " ");
            pre(tree.right);
        }
    }

    /**
     * 后序遍历
     *
     * @param tree 二叉树
     */
    private static void after(TreeNode<Integer> tree) {

        if (null != tree) {
            pre(tree.left);
            pre(tree.right);
            System.out.print(tree.data + " ");
        }
    }

    /**
     * 查找值所在树的结点
     *
     * @param tree  树
     * @param value 值
     * @return 结点
     */
    public static TreeNode<Integer> getNode(TreeNode<Integer> tree, int value) {

        if (null != tree) {
            int compare = tree.getData() - value;
            if (0 == compare) {
                return tree;
            } else if (0 < compare) {
                return getNode(tree.getLeft(), value);
            } else {
                return getNode(tree.getRight(), value);
            }
        }
        return null;
    }

    /**
     * 删除树结点元素
     *
     * @param tree 删除前树
     * @param data 元素数据
     * @return 删除之后的树
     */
    public static TreeNode<Integer> remove(TreeNode<Integer> tree, int data) {

        TreeNode<Integer> node = getNode(tree, data);
        if (null == node) {
            return null;
        }

        TreeNode<Integer> left = node.left;
        TreeNode<Integer> right = node.right;
        TreeNode<Integer> parent = node.parent;

        // 无左无右
        if (left == null && right == null) {
            if (parent.left == node) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        }

        // 有左无右
        if (left != null && right == null) {
            if (parent.left == node) {
                parent.left = left;
            } else {
                parent.right = left;
            }
        }

        // 无左有右
        if (left == null && right != null) {
            if (parent.left == node) {
                parent.left = right;
            } else {
                parent.right = right;
            }
        }

        // 有左有右
        if (left != null && right != null) {
            TreeNode<Integer> smallestNode = getRightSmallestNode(node);
            if (parent.left == node) {
                parent.left = smallestNode;
            } else {
                parent.right = smallestNode;
            }
            smallestNode.parent = parent;
        }

        return tree;
    }

    /**
     * 获取当前结点下右子树最小的结点(右边最小的都比当前的大)
     *
     * @param node 当前结点
     * @return 结点右子树下最小的结点
     */
    private static TreeNode<Integer> getRightSmallestNode(TreeNode<Integer> node) {

        TreeNode<Integer> right = node.right;
        if (right.left == null) { // 没有左结点
            return right;
        }
        return getRightSmallestNode(right);
    }

    /**
     * 树定义
     *
     * @param <T> 树结点数据
     */
    static class TreeNode<T> implements Serializable {

        private final T data; // data

        private TreeNode<T> parent; // parent Node

        private TreeNode<T> left; // left node

        private TreeNode<T> right; // right node

        public TreeNode(T data, TreeNode<T> left, TreeNode<T> right, TreeNode<T> parent) {
            this.data = data;
            this.left = left;
            this.right = right;
            this.parent = parent;
        }

        public T getData() {
            return data;
        }

        public TreeNode<T> getLeft() {
            return left;
        }

        public void setLeft(TreeNode<T> left) {
            this.left = left;
        }

        public TreeNode<T> getRight() {
            return right;
        }

        public void setRight(TreeNode<T> right) {
            this.right = right;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "data=" + data +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }

        public TreeNode<T> getParent() {
            return parent;
        }

        public void setParent(TreeNode<T> parent) {
            this.parent = parent;
        }
    }
}
